/*
 * NyuHash.hpp
 *
 *  Created on: 2010/05/23
 *      Author: mitsu
 */

#ifndef NYUHASH_HPP_
#define NYUHASH_HPP_

#include "NyuContext.hpp"

template<typename Key, typename Val>
class NyuHash {
public:
    NyuHash() : ents_(new Entry*[INITIAL_NENTS]), nents_(INITIAL_NENTS),
                size_(0) {
        ::memset(ents_, 0, sizeof(Entry*) * 7);
    }

    ~NyuHash() {
        for (int i = 0, j = nents_; i < j; i++) {
            delete ents_[i];
        }
        delete[] ents_;
    }

    size_t size() const {
        return size_;
    }

    void put(Key key, Val value, NyuContext* c) {
        unsigned int h = key->hash();
        unsigned int hh = h % nents_;
        int depth = 0;

        Entry* ent = ents_[hh];
        while (ent && !ent->key->opEq(NYU_OBJECT_TO_VALUE(key), c)) {
            ent = ent->next;
            ++depth;
        }

        if (ent) {
            ent->value = value;
            return;
        }

        ents_[hh] = new Entry(key, value, ents_[hh]);
        ++size_;

        if (depth > 2)
            rehash();
    }

    bool get(Key key, Val& value, NyuContext* c) {
        unsigned int h = key->hash();

        Entry* ent = ents_[h % nents_];
        while (ent && !ent->key->opEq(NYU_OBJECT_TO_VALUE(key), c)) {
            ent = ent->next;
        }

        if (ent) {
            value = ent->value;
            return true;
        }

        return false;
    }

    template<typename Func>
    void eachKeys(Func fn) {
        Entry** ents = ents_;

        for (size_t i = 0, j = nents_; i < j; i++) {
            for (Entry* ent = ents[i]; ent; ent = ent->next) {
                fn(ent->key);
            }
        }
    }

private:
    void rehash() {
        size_t new_size, i, j;
        Entry **new_ents, *ent, **ents;

        new_size = nents_ * 2 + 1;

        new_ents = new Entry*[new_size];

        ::memset(new_ents, 0, sizeof(Entry*) * new_size);

        ents = ents_;
        for (i = 0, j = nents_; i < j; i++) {
            for (ent = ents[i]; ent;) {
                Entry* tmp = ent;
                unsigned int h = tmp->key->hash() % new_size;
                ent = ent->next;
                tmp->next = new_ents[h];
                new_ents[h] = tmp;
            }
        }

        delete[] ents;

        nents_ = new_size;
        ents_ = new_ents;
    }

private:
    struct Entry {
        Key key;
        Val value;
        Entry* next;

        Entry(Key k, Val v, Entry* n = 0) :
            key(k), value(v), next(n) {
        }
        ~Entry() {
            delete next;
        }
    };

    Entry** ents_;
    size_t nents_;
    size_t size_;

    static const int INITIAL_NENTS = 7;
};

#endif /* NYUHASH_HPP_ */
